InforLorV4, Main, Exploration, bibRecord, 006376

Closure properties and decision problems of dag automata

Identifieur interne : 006376 ( Main/Exploration ); précédent : 006375; suivant : 006377

Closure properties and decision problems of dag automata

Auteurs : Siva Anantharaman [France] ; Paliath Narendran [États-Unis] ; Michael Rusinowitch [France]

Source :

Information processing letters [ 0020-0190 ] ; 2005.

RBID : Pascal:05-0215586

Descripteurs français

Pascal (Inist)
- Automate arbre, Automate déterministe, Complémentation, Temps polynomial, Résolution problème, Problème NP complet, Langage formel, Informatique théorique, Traitement information, Analyse algorithme, 05C05, 68T20, 46C07, Déterminisme, 68Q45, Problème universalité.

English descriptors

KwdEn :
- Algorithm analysis, Complementation, Computer theory, Deterministic automaton, Formal language, Information processing, NP complete problem, Polynomial time, Problem solving, Tree automaton, Universality problem.

Abstract

Tree automata are widely used in various contexts. They are closed under boolean operations and their emptiness problem is decidable in polynomial time. Dag automata are natural extensions of tree automata, operating on dags instead of on trees; they can also be used for solving problems. Our purpose in this paper is to show that algebraically they behave differently: the class of dag automata is not closed under complementation, dag automata are not determinizable, their membership problem is NP-complete, the universality problem is undecidable, and the emptiness problem is NP-complete even for deterministic labeled dag automata.

Affiliations:

France, États-Unis

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000575
to stream PascalFrancis, to step Curation: 000463
to stream PascalFrancis, to step Checkpoint: 000515
to stream Main, to step Merge: 006652
to stream Main, to step Curation: 006376

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Closure properties and decision problems of dag automata</title>
<author><name sortKey="Anantharaman, Siva" sort="Anantharaman, Siva" uniqKey="Anantharaman S" first="Siva" last="Anantharaman">Siva Anantharaman</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LIFO, Universlté d'Orléans</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>Universlté d'Orléans</wicri:noRegion>
<wicri:noRegion>LIFO, Universlté d'Orléans</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Narendran, Paliath" sort="Narendran, Paliath" uniqKey="Narendran P" first="Paliath" last="Narendran">Paliath Narendran</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>University at Albany, SUNY</s1>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>University at Albany, SUNY</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michael" last="Rusinowitch">Michael Rusinowitch</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>LORIA - Nancy</s1>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>LORIA - Nancy</wicri:noRegion>
<wicri:noRegion>LORIA - Nancy</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">05-0215586</idno>
<date when="2005">2005</date>
<idno type="stanalyst">PASCAL 05-0215586 INIST</idno>
<idno type="RBID">Pascal:05-0215586</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000575</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000463</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000515</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000515</idno>
<idno type="wicri:doubleKey">0020-0190:2005:Anantharaman S:closure:properties:and</idno>
<idno type="wicri:Area/Main/Merge">006652</idno>
<idno type="wicri:Area/Main/Curation">006376</idno>
<idno type="wicri:Area/Main/Exploration">006376</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Closure properties and decision problems of dag automata</title>
<author><name sortKey="Anantharaman, Siva" sort="Anantharaman, Siva" uniqKey="Anantharaman S" first="Siva" last="Anantharaman">Siva Anantharaman</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LIFO, Universlté d'Orléans</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>Universlté d'Orléans</wicri:noRegion>
<wicri:noRegion>LIFO, Universlté d'Orléans</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Narendran, Paliath" sort="Narendran, Paliath" uniqKey="Narendran P" first="Paliath" last="Narendran">Paliath Narendran</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>University at Albany, SUNY</s1>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>University at Albany, SUNY</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michael" last="Rusinowitch">Michael Rusinowitch</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>LORIA - Nancy</s1>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>France</country>
<wicri:noRegion>LORIA - Nancy</wicri:noRegion>
<wicri:noRegion>LORIA - Nancy</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Information processing letters</title>
<title level="j" type="abbreviated">Inf. process. lett.</title>
<idno type="ISSN">0020-0190</idno>
<imprint><date when="2005">2005</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Information processing letters</title>
<title level="j" type="abbreviated">Inf. process. lett.</title>
<idno type="ISSN">0020-0190</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm analysis</term>
<term>Complementation</term>
<term>Computer theory</term>
<term>Deterministic automaton</term>
<term>Formal language</term>
<term>Information processing</term>
<term>NP complete problem</term>
<term>Polynomial time</term>
<term>Problem solving</term>
<term>Tree automaton</term>
<term>Universality problem</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Automate arbre</term>
<term>Automate déterministe</term>
<term>Complémentation</term>
<term>Temps polynomial</term>
<term>Résolution problème</term>
<term>Problème NP complet</term>
<term>Langage formel</term>
<term>Informatique théorique</term>
<term>Traitement information</term>
<term>Analyse algorithme</term>
<term>05C05</term>
<term>68T20</term>
<term>46C07</term>
<term>Déterminisme</term>
<term>68Q45</term>
<term>Problème universalité</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Tree automata are widely used in various contexts. They are closed under boolean operations and their emptiness problem is decidable in polynomial time. Dag automata are natural extensions of tree automata, operating on dags instead of on trees; they can also be used for solving problems. Our purpose in this paper is to show that algebraically they behave differently: the class of dag automata is not closed under complementation, dag automata are not determinizable, their membership problem is NP-complete, the universality problem is undecidable, and the emptiness problem is NP-complete even for deterministic labeled dag automata.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
</list>
<tree><country name="France"><noRegion><name sortKey="Anantharaman, Siva" sort="Anantharaman, Siva" uniqKey="Anantharaman S" first="Siva" last="Anantharaman">Siva Anantharaman</name>
</noRegion>
<name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michael" last="Rusinowitch">Michael Rusinowitch</name>
</country>
<country name="États-Unis"><noRegion><name sortKey="Narendran, Paliath" sort="Narendran, Paliath" uniqKey="Narendran P" first="Paliath" last="Narendran">Paliath Narendran</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006376 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006376 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:05-0215586
   |texte=   Closure properties and decision problems of dag automata
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Closure properties and decision problems of dag automata

Closure properties and decision problems of dag automata

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri